package main

import (
	"fmt"
)

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */

type Node struct {
	Val    int
	Next   *Node
	Random *Node
}

func createLine(valList [][]int) *Node {
	head := &Node{}
	var nodeList []*Node
	cur := head
	for _, val := range valList {
		n := &Node{Val: val[0]}
		nodeList = append(nodeList, n)
		cur.Next = n
		cur = cur.Next
	}
	for i := range valList {
		if valList[i][1] != -1 {
			nodeList[i].Random = nodeList[valList[i][1]]
		}
	}
	return head.Next
}

func printLine(head *Node) {
	for head != nil {
		fmt.Print(head.Val, " --> ")
		head = head.Next
	}
	fmt.Println("end")
}

func copyRandomList(head *Node) *Node {
	if head == nil {
		return nil
	}
	var nodeList []*Node           // 记录所有新的节点列表
	nodeCache := map[*Node]*Node{} // 构建老节点到新节点的映射

	nodeCur := head
	for nodeCur != nil {
		nodeNew := &Node{Val: nodeCur.Val}
		nodeList = append(nodeList, nodeNew)
		nodeCache[nodeCur] = nodeNew
		nodeCur = nodeCur.Next
	}
	nodeList = append(nodeList, nil)
	nodeCur, nodeIdx := head, 0

	for nodeCur != nil {
		nodeList[nodeIdx].Random = nodeCache[nodeCur.Random]
		nodeList[nodeIdx].Next = nodeList[nodeIdx+1]
		nodeCur = nodeCur.Next
		nodeIdx++
	}
	return nodeList[0]
}

func main() {
	head := createLine([][]int{{7, -1}, {13, 0}, {11, 4}, {10, 2}, {1, 0}})
	printLine(head)
	printLine(copyRandomList(head))
}
